package leetcode.array;

import leetcode.Hot100.permute;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * <p>
 * 你可以按 任何顺序 返回答案。
 * https://leetcode-cn.com/problems/combinations/
 * @version 1.0
 * @date 2022/1/1 16:33
 *
 * 回溯 + 剪枝的经典题 面试题
 * @see permute 注意比较着两题的回溯算法和深度优先搜索
 */
public class combine {

    public static void main(String[] args) {
        combine(4, 2);
    }

    // 1 <= n <= 20
    // 1 <= k <= n
    // C(n,k) 的组合情况
    static public List<List<Integer>> combine(int n, int k) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        List<List<Integer>> res = new ArrayList<>();
        dfs1(arr, k, 0, new ArrayList<>(), res);
        return res;
    }

    // 1, 2, 3, 4
    // 深度优先遍历的过程（n=4，k=2）
    // 1
    // 2,3,4
    // 2
    // 3,4
    // 3
    // 4
    static void dfs(int[] arr, int k, int startIndex, List<Integer> combineList, List<List<Integer>> res) {
        if (k == combineList.size()) {
            res.add(new ArrayList<>(combineList));
        } else {
            for (int i = startIndex; i < arr.length; i++) {
                combineList.add(arr[i]);
                // 注意 startIndex = i + 1，是因为递归的过程中，不能再次选择 i+1 前面的元素
                dfs(arr, k, i + 1, combineList, res);
                combineList.remove(combineList.size() - 1);
            }
        }
    }

    // https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/
    // 回溯过程的剪枝操作 dfs方法和dfs1 只有 for循环的条件不同。这里条件不太好找，最好在纸上画画，找找规律
    // 我们知道 k - combineList.size() 是还需要的数组元素个数，如果当前递归中，数组还剩的个数不能满足combineList还需的个数，就提前终止
    static void dfs1(int[] arr, int k, int startIndex, List<Integer> combineList, List<List<Integer>> res) {
        if (k == combineList.size()) {
            res.add(new ArrayList<>(combineList));
        } else {
            for (int i = startIndex; i <= arr.length - (k - combineList.size()); i++) {
                combineList.add(arr[i]);
                // 注意 startIndex = i + 1，是因为递归的过程中，不能再次选择 i+1 前面的元素
                dfs1(arr, k, i + 1, combineList, res);
                combineList.remove(combineList.size() - 1);
            }
        }
    }
}
